#include <iostream>
#include <vector>
#include <stack>
#define  maxsize 100
using namespace std;

int flag [maxsize];
int indegree[maxsize];
vector < vector<int>>v;
stack<int> s;

/**
   拓扑排序法判断有向图是否有环
//开辟一个indegree 在输入图的有关信息的时候对indegree进行初始化 存放每个节点的入度
//扫描一遍indegree 将入度为0的结点入栈
//只要栈不空每次从栈里面取出一个结点将其指向的结点的入度全部-1  如果出现度为0的结点继续入栈
//每次都栈里面取出一个结点都将全局变量cnt++
//循环结束判断cnt==n 如果不等说明该图存在环

 */


/**
 *  使用dfs判断有向图是否有环
 *  使用一个flag数组记录每一个结点的访问状态   0 1 2  //0表示尚未访问 1表示正在访问但没有结束递归 2表示访问结束递归结束
 *  如果出先两个 状态都为1 则说明存在环
 *
 *
 * @return
 */


void dfs(int i)
{
    //访问
    flag[i]=1;
    for(int j=0;i<v[i].size();++j)
    {
        if(flag[v[i][j]]==0)
        {
            dfs(v[i][j]);
        }
        else if(flag[v[i][j]]==1)
        {
            cout<<"存在环路";
            return ;

        }
    }
    flag[i]=2;
}

int main() {
    /**
     *  拓扑排序法
     */
//    int m,n;
//    int a,b;
//    int cnt=0;//记录输出的顶点个数
//
//    //输出边和个数和顶点
//    //构造有向图
//    cin>>m>>n;
//    while(m--)
//    {
//       cin>>a>>b;
//       v[a].push_back(b);
//       indegree[b]++;
//    }
//    //扫描一下indegree找出度为0的点压栈
//    for(int i=0;i<n;++i)
//    {
//        if(indegree[i]==0)
//        {
//            s.push(i);
//        }
//    }
//    while(!s.empty())
//    {
//        int top=s.top();
//        cnt++;
//        cout<<top<<" ";
//        s.pop();
//        for(int i=0;i<v[top].size();++i)
//        {
//            indegree[v[top][i]]--;
//            if(indegree[v[top][i]]==0)
//            {
//                s.push(i);
//            }
//        }
//    }
//    if(cnt!=n)
//        cout<<"该有向图存在环";


   /**
    * 图的深度遍历法
    */
    int flag=0;// 0 1 2 三种状态   1遇到1就表明



    return 0;
}
